package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
	
	Note: You can only move either down or right at any point in time.
	
	Example 1:
	
	[[1,3,1],
	 [1,5,1],
	 [4,2,1]]
	
	Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum. 
题目大意
	　　
解题思路
	设dp[i][j]表示从左上角到grid[i][j]的最小路径和。那么dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1] );
   动态规划
   TODO:
 * @Date 2017-10-21 20：20
 */
public class _064_Minimum_Path_Sum {
	
    public int minPathSum(int[][] grid) {
   
    	if (grid==null)		return 0;
        int m = grid.length, n = grid[0].length;
        if (m==0 || n==0)	return 0;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        //
        for (int i = 1; i < m; i ++) {
        	dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        //
        for (int j = 0; j < n; j ++) {
        	dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        //
        for (int i = 1; i < m; i ++) { 
        	for (int j = 1; j < n; j ++) {
        		dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        	}
        }
        return dp[m-1][n-1];
    }
	public static void main(String[] args) {
		_064_Minimum_Path_Sum obj = new _064_Minimum_Path_Sum();

		obj.minPathSum(new int[][]
				{
					{1, 3, 1},
					{1, 5, 1},
					{4, 2, 1}
				});
	}

}
